/**
 * DNA序列由一系列核苷酸组成，缩写为'A','C','G'和'T'.。
 * 例如，"ACGAATTCCG"是一个 DNA序列 。
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
 *
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的长度为10的序列(子字符串)。你可以按 任意顺序 返回答案。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/repeated-dna-sequences
 */
/**在最低位添加一个数字
int number = 8264;
 number 的进制
        int R = 10;
 想在 number 的最低位添加的数字
        int appendVal = 3;
 运算，在最低位添加一位
        number = R * number + appendVal;
 此时 number = 82643

        /* 在最高位删除一个数字 */
/**
 * int number = 8264;
 number 的进制
        int R = 10;
 number 最高位的数字
        int removeVal = 8;
 此时 number 的位数
        int L = 4;
 运算，删除最高位数字
        number = number - removeVal * R^(L-1);
 此时 number = 264
*/
class FindRepeatedDnaSequences {
    /**
     * 滑动哈希技巧法（最优的）
     * @param s
     * @return
     *们用一个 10 位数来标识一个长度为 10 的碱基字符序列，这需要 long 类型存储，int 存不下 10 位数。但你注意这个 10 位数中所有的数字只会局限于 0,1,2,3，是不是有些浪费？
     *
     * 换句话说，我们需要存储的其实只是一个四进制下的十位数（共包含 4^10 个数字），却用了十进制的十位数（可以包含 10^10 个数字）来保存，显然是有些浪费的。
     *
     * 因为 4^10 = 1048576 < 10^8，所以只要我们在四进制的运算规则下进行运算，十进制的八位数就能存下，这样的话 int 类型就够用了，不需要 long 类型。
     *
     * 具体来说，只要改变我们之前那两个公式的进制 R 就行了
     */
    public List<String> findRepeatedDnaSequencesHuaDonHash(String s) {
        // 先把字符串转化成四进制的数字数组
        int[] nums = new int[s.length()];
        for (int i = 0; i < nums.length; i++) {
            switch (s.charAt(i)) {
                case 'A':
                    nums[i] = 0;
                    break;
                case 'G':
                    nums[i] = 1;
                    break;
                case 'C':
                    nums[i] = 2;
                    break;
                case 'T':
                    nums[i] = 3;
                    break;
            }
        }
        // 记录重复出现的哈希值
        HashSet<Integer> seen = new HashSet<>();
        // 记录重复出现的字符串结果
        HashSet<String> res = new HashSet<>();

        // 数字位数
        int L = 10;
        // 进制
        int R = 4;
        // 存储 R^(L - 1) 的结果
        int RL = (int) Math.pow(R, L - 1);
        // 维护滑动窗口中字符串的哈希值
        int windowHash = 0;

        // 滑动窗口代码框架，时间 O(N)
        int left = 0, right = 0;
        while (right < nums.length) {
            // 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）
            windowHash = R * windowHash + nums[right];
            right++;

            // 当子串的长度达到要求
            if (right - left == L) {
                // 根据哈希值判断是否曾经出现过相同的子串
                if (seen.contains(windowHash)) {
                    // 当前窗口中的子串是重复出现的
                    res.add(s.substring(left, right));
                } else {
                    // 当前窗口中的子串之前没有出现过，记下来
                    seen.add(windowHash);
                }
                // 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）
                windowHash = windowHash - nums[left] * RL;
                left++;
            }
        }
        // 转化成题目要求的 List 类型
        return new LinkedList<>(res);
    }

    /**
     * 滑动窗口解法（第二优的解法）
     *你应该不难理解。但你注意这个解法依然需要将窗口中的字符转化成字符串然后去
     * se 集合判断是否存在重复，你一旦想把字符转化成字符串，就难免需要 O(L) 的时间来操作。所以这个算法的时间复杂度还是没有降低，依然是 O(NL)。
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequencesHuaDon(String s) {
        StringBuilder ans = new StringBuilder();
        int left = 0;
        int right = 0;
        int len = s.length();
        Set<String> set = new HashSet<>();
        Set<String> ret = new HashSet<>();
        while (right < len) {
            ans.append(s.charAt(right));
            right++;
            if (right - left == 10) {
                String tmp = ans.toString();
                if (set.contains(tmp)) {
                    ret.add(tmp);
                } else {
                    set.add(tmp);
                }
                ans.delete(0, 1);
                left++;
            }
        }
        return new ArrayList<>(ret);
    }

    /**
     * 暴力解法（最笨的解法）
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequencesBaoLi(String s) {
        int n = s.length();
        // 记录出现过的子串
        HashSet<String> seen = new HashSet();
        // 记录那些重复出现多次的子串
        // 注意要用哈希集合，防止记录重复的结果
        HashSet<String> res = new HashSet<>();

        for (int i = 0; i + 10 <= n; i++) {
            String subStr = s.substring(i, i + 10);
            if (seen.contains(subStr)) {
                // 之前出现过，找到一个重复的
                res.add(subStr);
            } else {
                // 之前没出现过，加入集合
                seen.add(subStr);
            }
        }
        return new LinkedList<>(res);
    }
}